package algorithm_primary.studyClass.新手课程;

import java.util.Arrays;

/**
 * @author 衡孟浩
 * @date 2023/5/27 15:07
 */
public class 局部最小 {
    public static void main(String[] args) {
        int time = 100000;
        // 随机生成最大数组长度
        int maxLen = 20;
        // 随机生成最大值
        int maxValue = 100;
        for (int i = 0; i < time; i++) {

            int[] arr = createArr(maxLen, maxValue);
            int juBuMinValue = juBuMinValue(arr);
            if (!check(arr, juBuMinValue)) {
                System.out.println("--------生成数组为:\n" + Arrays.toString(arr));
                System.out.println("局部最小值为:" + maxValue);
            }


        }
    }

    /**
     * 可以使用二分查找
     * @param nums
     * @return
     */
    public static int juBuMinValue(int[] nums) {
        int l = 0, r = nums.length - 1, mid = 0;
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1 || nums[0] < nums[1]) {
            return l;
        }
        if (nums[r - 1] > nums[r]) {
            return r;
        }
        /**
         * 想象成为一个抛物线 就可以了    下边的  就是   只有当是
         * 左边一个向下的线  右边一个向上的线才会百分百存在局部最小
         * .            .
         *   . -------.
         *
         *
         * .
         *   .  ----.           .----        .
         *             .---.              .
         *
         */
        //  使用   l < r-1  这样是为了确保   当前肯定是有三个数在 l --- r  这个区间的  要不然就会出现一个问题   当前mid就是0 然后 mid - 1 就是错误的的
        while (l <= r - 1) {
            mid = (r + l) / 2;
            // 只有当mid的上一个大于mid   mid的下一个大于mid  这时候就是要给局部最小
            if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1]) {
                return mid;
            } else if (nums[mid] > nums[mid - 1]) {
                // 如果mid大于他的上一个   说明最小值肯定在 l和mid之间这时候改变r的位置
                r = mid - 1;
            } else if (nums[mid] > nums[mid + 1]) {
                // 如果mid大于他的下一个   说明最小值肯定在 r和mid之间这时候改变l的位置
                l = mid + 1;
            }
        }
        return -1;
    }


    public static boolean check(int[] nums, int minValue) {
        if (minValue == -1){
            return true;
        }
        int left = minValue - 1;
        int right = minValue + 1;
        boolean checkLeft = left < 0 || nums[left] > nums[minValue];
        boolean checkRight = right > (nums.length - 1) || nums[right] > nums[minValue];
        return checkLeft && checkRight;
    }


    public static int[] createArr(int maxLenth, int maxValue) {
        int[] arr = new int[maxLenth];
        int zero = (int) (Math.random() * maxValue);
        arr[0] = zero;
        for (int i = 1; i < arr.length; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue);
            } while (arr[i] == arr[i - 1]);
        }

        return arr;
    }
}
